T=20;
n=[92,100,91,96,99,96,98,93,93,99,97,94,92,100,96,99,94,97,98,97];
a=[10630,3021,13817,11024,10028,16426,8217,6423,2624,7019,14019,15027,12618,9217,2826,7429,14823,14421,6828,14630,5217,7626,17818,9430,6626,5821,17023,17624,9617,11227,15618,13024,8628,18025,18229,4431,16226,4623,6029,5616,11627,15221,16825,11823,19823,2419,4217,3428,19424,19231,12428,5424,15820,14225,15429,12024,3222,8420,5028,18626,17226,16030,13218,18825,3624,9025,2016,13418,9821,12817,3822,20020,6219,10427,2230,17424,8825,8019,4822,11423,10818,4020,7231,13627,19016,19631,1830,18424,16617,12224,10230,7816,3396,8796,16597,2598,20197,6596,10397,14196,4996,8997,4397,9798,11598,8596,19996,6397,3196,12798,15197,1798,18598,18398,19397,6198,13198,5596,12598,4796,17596,20397,18997,20596,9998,6998,14996,11197,13596,15797,19596,13797,10796,12196,2796,7397,11797,14597,2198,16998,7996,6796,10197,18198,2396,12396,9197,9397,19796,5398,15997,18798,9596,13997,8197,1598,13397,20796,7198,14796,8397,16798,11998,14397,17797,15597,4196,7797,16396,5198,3597,7596,3797,12996,21198,4598,2998,17196,16198,20996,3997,5796,19197,17396,10998,5998,15397,1996,1397,11398,17997,10597,11420,4820,13220,16020,5820,6820,11220,7220,4220,15020,3420,14820,2020,13420,3020,18220,14620,17220,9420,13820,6620,12420,17620,12020,19420,6020,5620,18420,13020,14220,8020,16620,11820,5020,12620,15820,9620,19620,5220,8220,3820,15420,17820,13620,2220,8420,14420,10820,18020,7620,10420,19020,4620,16820,3620,9820,2620,14020,2420,19220,2820,11020,15620,17420,16220,16420,6220,10220,7420,4420,6420,18820,3220,7020,1820,9220,19820,15220,10620,11620,5420,8820,4020,7820,18620,10020,9020,12820,12220,17020,8620,14520,18519,19919,16520,8521,13123,5719,18922,7720,2920,15124,18121,6923,6523,6324,1721,17124,5919,1522,5520,14722,2120,3523,13922,1920,12119,3321,17519,13319,1324,15521,20321,16723,8321,15324,3724,17723,17320,15724,2322,10921,3124,16122,9524,13520,14923,9122,19524,11120,8920,4924,16320,5123,18323,12321,3919,18720,7123,12719,20124,10320,2723,9919,19724,8722,7924,19124,4524,2522,19319,9319,14123,11722,14319,13720,11322,4119,4724,7523,7322,6720,12520,6119,10120,8124,10719,5324,17921,10523,11924,11523,12919,9723,15920,16920,4323,18719,20324,13318,3725,10919,5724,16720,14723,20717,12716,7922,13521,12121,13926,5523,14317,9121,10720,3916,7318,6716,5925,8924,9923,17720,11318,8524,15920,9324,4519,7716,2919,20522,14916,1124,16125,11721,19317,15123,8725,11916,13119,19721,6919,19517,17917,8325,11522,16920,6119,2517,17117,12522,15722,14517,9525,4121,14125,2726,1520,6526,15321,19123,5325,18923,7516,3324,16518,10519,1323,20117,19922,9726,5118,4318,1726,12918,18524,11125,10124,12319,8119,13724,2122,7120,18320,3118,17316,6318,17520,4716,15522,4926,2317,1924,18121,16320,3523,10316,2101,13498,2701,17699,6899,14098,15099,1898,15900,5698,18501,9901,20701,5098,12299,15698,14501,9700,10301,20099,18099,10499,18300,9498,16699,16101,3301,11101,9299,15500,10901,11701,2300,16300,11301,2900,6298,6099,11501,7499,12498,4901,20901,14899,13899,5301,12098,9099,16498,19898,12698,13699,17498,19700,5501,2501,20298,20501,7298,4299,3499,11898,18698,12900,3899,3701,6698,19298,8701,14299,17899,8899,5900,4498,10098,16901,13300,17101,10701,8498,8100,4701,13098,7899,7701,19100,15300,4100,18898,17298,7100,19498,6498,3099,14699,8299,4691,16298,3099,1903,19296,3903,4492,1705,11492,16103,18102,14306,6697,18291,6103,18903,15506,14898,15306,9702,14094,10098,12503,19705,11891,20292,10501,16496,9107,13506,6500,2094,4305,19899,13299,3303,6895,11101,20895,12692,12900,15703,17496,3507,15103,13100,7493,13697,4900,16696,9507,20091,16897,2305,9896,11299,15894,2903,5501,17297,8307,20696,11699,14501,18507,14698,17898,5294,7900,4095,8094,7702,19506,8894,7102,2698,5698,7295,8503,12091,17697,10895,5895,5093,17091,8696,3699,20500,12291,6305,1502,9299,13903,10301,10703,19107,18705,2498,5649,14249,1655,16247,11856,2446,9257,14445,3446,9447,6055,7650,12448,10856,8853,16455,8250,17055,6249,2850,18846,17257,3055,8052,2644,11054,12047,9648,5455,13853,19653,18649,1457,10054,10248,2044,6456,2250,13644,7251,10445,4049,12850,17449,6850,3854,1845,17844,18050,17645,13454,11246,18251,7857,9049,8655,12652,4253,15247,12254,1257,15444,15646,8448,15053,7057,9854,4456,3256,14655,11454,4655,3656,19050,11655,7446,4844,16055,5856,6647,13044,10649,15857,5044,16656,14048,13248,18453,14854,5247,16851,19247,19445,5033,16626,14828,11030,19436,15035,17826,16034,11827,8435,6826,2232,15836,10030,4026,2428,9029,5634,13035,8628,18628,3031,12430,5830,6026,7231,10229,16826,12826,19626,18428,3430,8234,7429,19235,7834,18227,6228,13832,13432,17236,8828,16430,10827,2632,10434,18029,17431,17028,1635,14030,14431,6427,13635,1832,9636,15630,11636,2036,14629,12635,15428,3234,11426,7631,12232,4836,3827,3628,5226,5429,4236,14234,17627,9433,16227,12026,4426,2833,7029,11236,15227,10636,8036,13231,19034,6626,4632,1233,9834,1436,9229,18831,12430,3032,7431,1831,18632,16431,11831,14830,6630,14630,5830,14030,4630,2630,16230,15032,9432,5031,3230,17831,17230,1430,15630,2032,2431,4430,5231,18430,2831,10631,18231,5431,8430,16032,20431,8630,11230,20832,19432,18831,15431,19631,16831,19831,16630,13231,12831,13430,13831,3431,12232,6232,19031,2232,6432,20032,14231,5631,8032,10032,17032,7631,6030,8232,20632,1230,13030,7031,17431,3831,9832,9631,19230,1632,11030,9230,12631,10431,8831,4832,3631,10232,7832,6832,14430,17632,18032,11632,11432,4030,10831,20230,4231,13632,12032,7232,15230,15832,9031,2485,18486,19085,7686,1887,20285,16085,12485,2286,5886,10487,16685,16886,9287,2686,4287,19287,9086,12885,12087,4886,13687,13485,8685,1685,7286,5287,10286,17486,3486,11287,10886,6887,13086,16485,19686,18286,7885,8087,16287,11487,9487,12687,14087,19486,5686,14286,12286,5487,4685,17686,20686,8887,20485,8287,9687,14486,8485,7086,6286,20887,18885,6687,2885,20087,17885,11087,13885,15887,15487,15087,10085,6485,19887,15286,2085,18085,4085,6086,14885,14686,3887,3686,11887,3087,13285,7487,9886,3285,5085,17085,11687,17285,18685,4487,15685,10687,16656,4255,2459,12255,11859,7861,6658,4456,8459,5258,10455,6255,15257,19456,6859,19255,12053,4659,13659,19657,6055,7060,7456,18259,12659,7255,11653,3253,3461,11460,18060,18858,9857,4860,18457,8256,5859,14860,2057,4054,2660,3655,9659,16855,17255,3059,9259,15656,15053,1457,16054,1055,8861,12460,19053,10261,13058,17053,8660,10653,10061,13257,15857,9056,14057,17861,6457,1859,5656,2254,14659,12859,3854,15455,1658,11059,18658,14454,16258,8055,16454,7656,17456,14260,13454,9459,13861,17654,5455,10855,11255,1255,5056,2858,11924,11130,5924,3130,17319,7517,4328,14923,9728,4125,17726,12322,9529,7720,13729,2129,5718,15129,7321,16322,12527,15929,2716,16915,9323,3720,6116,10315,17524,1715,11325,11521,10918,19330,14716,13127,19715,6722,19122,11723,2324,15327,4730,12716,14118,10518,9120,18120,16523,8327,12122,2915,10722,18925,15717,3323,4516,6519,3915,8516,16128,2520,7127,16721,1529,7925,12917,1917,14327,8716,8920,18729,5324,17921,14515,13919,18515,18326,13321,10126,5523,5128,9930,6930,13520,3522,19526,8123,15528,6322,4928,17128,7708,4317,16721,3523,1309,12908,3717,2509,13109,7119,6713,19316,13308,1523,20109,17116,10310,19723,5517,16916,19112,18313,4118,20708,10511,7319,6312,14712,11522,15724,5724,8322,14512,15309,15912,17323,16317,5913,18514,2113,12308,6916,15522,11323,13917,3116,18109,4514,13722,18913,12510,14924,8521,4720,11722,11110,2923,12722,12115,3310,6513,18715,9120,2315,1920,20514,7514,2716,5309,10921,16523,15117,9515,17518,1123,7924,1722,9720,4910,8111,8910,5123,6111,8720,10113,3924,20910,9922,13521,10709,9318,19912,19515,14319,17917,16118,17711,14114,11918,20316,12525,18713,1313,6315,16720,5717,19321,14112,20116,10924,17313,16925,1911,14520,7516,13923,8317,6714,17514,2919,13515,18515,10720,5311,9516,5920,4111,17925,9723,16324,3513,7323,15725,10515,7913,15913,8123,9116,17123,6115,19713,1521,12921,17724,6924,12320,3711,11311,3319,15323,16520,4514,8516,8924,7118,3123,8717,13714,19517,6521,2711,2324,5513,18917,7722,19920,13111,19111,5113,10314,18121,15515,11924,14319,4915,12722,9920,4318,20311,18325,16123,12114,11711,13321,1720,9312,14720,2523,2119,11523,15123,3917,11121,14911,10115,4722,4719,5120,4119,12519,11519,10320,3320,10921,3718,2116,16917,16116,9517,2716,9316,16521,6716,5519,12718,17521,14121,12918,19317,6519,11319,15318,19919,12119,20319,8916,3916,6920,15919,20916,15519,11116,5920,15721,9721,13116,7320,8118,4321,7916,2918,8719,15117,4516,14518,18520,3517,13520,6321,19120,11918,16717,18120,2519,6118,17317,16319,13319,14920,13919,20519,18719,10519,18919,17116,11719,9920,18318,17917,5321,7118,20121,21516,10118,8316,20721,5720,17716,3119,10716,13717,1919,4920,19521,8517,14716,14316,21316,7716,21120,19719,12316,9116,7520,2318,12938,14938,19938,15539,2538,9539,4539,15737,16939,6737,14737,20339,7538,8537,10937,4738,13938,6339,16538,14139,3138,12537,19137,2137,15338,3939,12738,8338,18537,7337,17137,16139,7139,3338,20137,10739,9738,5337,8137,12139,9139,10338,18137,17937,5738,5139,2737,6537,15937,9939,17337,7938,16739,10538,18739,12338,4137,13139,15137,19538,13737,4337,2938,3738,4938,13537,17738,10137,18339,11939,6137,14537,8938,7737,17539,11339,11537,9338,11138,2338,5537,13339,1738,8738,19738,18939,5939,19339,3537,14338,16339,6938,1939,11738,11727,20534,19528,4923,19928,12520,15930,5729,7925,9327,7532,20725,19131,16327,12924,15316,16527,11926,1930,2522,5934,4719,13321,12719,17116,10524,18133,8719,15134,9928,20921,4516,18327,19724,16932,8331,5523,7723,8534,18523,3723,2121,10121,20333,3932,2726,11321,18722,10922,3322,14934,6331,17517,14529,2931,7131,14725,9525,2325,21124,18922,14317,9131,10321,17721,8131,13119,13934,15530,19334,8928,17316,13534,5326,3526,5120,6131,14132,12131,6723,20124,4323,10731,3120,4118,15729,6526,6932,11530,12317,13720,16134,11132,9724,7322,16722,17931,4043,16052,6443,18044,1448,10049,18855,4254,11442,13455,3453,12441,14456,5244,2042,11849,6655,2452,12854,15247,16856,2242,8047,16656,18255,9455,14841,7656,12642,3848,4445,6052,11652,5451,19045,3645,8644,13642,10642,15645,8444,19648,11253,14052,3055,10855,14243,7449,12054,1250,19441,13251,9054,19251,18649,7255,5650,1652,10452,12242,5846,17052,3253,4841,2641,13854,17852,20053,19841,16446,10249,9645,17449,7852,18446,4652,8856,6248,13050,14653,9852,20254,1049,20450,15450,6850,9242,15052,17247,17647,1852,8248,15846,16251,2851,7042,5041,11042,5484,13482,13081,2287,14283,10684,16280,2687,19686,16089,9890,13681,3688,15088,6893,16489,7290,17488,7692,19490,17689,15490,14085,8291,3086,17091,2880,3483,2481,8491,5089,6279,1682,15687,9485,8079,4284,6086,12281,19283,18684,9288,4490,14893,13279,2080,16888,6482,12680,7091,10283,10884,8886,3889,11690,1492,4087,6679,13885,20088,3281,8690,14688,20290,11485,11283,11085,1283,17287,11893,10081,9091,5683,12487,5891,15885,19083,18886,12084,7489,5293,1888,4689,7879,16687,4891,20492,9683,12880,17892,10492,18280,14492,18483,18085,15291,19879];